Databases are used to store the data that is used by one or more software applications. Databases can be managed programmatically through structured query language (SQL) statements. There are generally two majority categories of SQL statements: data definition language (DDL) statements and data manipulation language (DML) statements. DDL statements are SQL statements that are designed to modify the structure of the database. An example of a DDL statement is a CREATE TABLE statement. DML statements, on the other hand, are SQL statements that insert or modify data in the database. An example of a DML statement is an INSERT statement that inserts new rows into one or more tables.
Data in a database is arranged according to a series of tables, with each table having one or columns of data, and one or more rows of data for these columns. Each table typically has one or more columns designated as keys that uniquely identify each row of data so that duplicates are not inserted into the same table. Keys are different from indexes, however. Indexes are designed to allow quick lookups of data in the tables. Data columns that are part of a key can also be used as indexes to the data, allowing rows to be located more quickly. Columns of data that are not actually keys can also serve as an index to the data, such as when that column contains data that is frequently accessed. A more detailed discussion on indexes will now be provided for the sake of background.
Indexes in a database are analogous to an index in the back of a printed book. When you want to locate a certain topic in a book, you look for a certain known word in an index, and the index then tells you the page number where that topic is located. An index in a database serves a similar function, and allows a computer to look up data in a table that matches a given index value.
Indexed columns in a database table are usually stored in an index structure called a B-Tree, but could also be in another type of table structure. A B-Tree maintains an ordered set of data that allows for a given index value to be quickly retrieved, deleted, and/or inserted. A B-Tree contains node records that point to other node records. To search the B-Tree to retrieve a value, the tree is traversed from node to node until the desired value is located, or because there are no more paths in the tree to search. A B-Tree structure is generally a much more efficient way of locating data than to search in sequential order to locate the desired value, especially when a large volume of data is present, which is usually the case with indexes.
When rows are inserted into a table in a database, index values for those inserted rows of data also need created. Thus, in addition to inserting the complete row into the table itself, an entry is also inserted into the table structure (e.g. B-Tree, etc.) that stores the indexed values for newly inserted rows. When a large number of new values need inserted into a table at once, the process of adding the new values can be much slower than when just a few values are being inserted.